#include <iostream>
#include <deque>
#include <iomanip>
#include <sstream>


#define SENSINEL -100000
using namespace std;

enum Color
{RED = 0,BLACK = 1};



typedef struct Interval
{
  double low;
  double high;
}Interval;



typedef struct Node
{
  Color color;
  struct Node *lc;
  struct Node *rc;
  struct Node *parent;
  Interval interval;
  double max;
  double key;
}Node;



typedef struct RBT
{
  Node *root;
  Node *nil;
}RBT;




double GetMax(double high, double leftMax, double rightMax)
{
  double temp;
  if (high > leftMax)
    {
      if (high > rightMax)
	temp = high;
      else temp = rightMax;
    }
  else if (leftMax > rightMax)
    temp = leftMax;
  else temp = rightMax;
  return temp;
};




void LeftRotate(RBT *rbt,Node *x)
{
  if (x->rc != rbt->nil)
    {
      Node *y = x->rc;
      x->rc = y->lc;
      if (y->lc != rbt->nil)
	y->lc->parent = x;
      y->parent = x->parent;
      if (x->parent == rbt->nil)
	rbt->root = y;
      else if (x == x->parent->lc)
	x->parent->lc = y;
      else x->parent->rc = y;
      y->lc = x;
      x->parent = y;

      x->max = GetMax(x->interval.high,x->lc->max,x->rc->max);
      y->max = GetMax(y->interval.high,y->lc->max,y->rc->max);
    }
  else cout << "Error!" << endl;
};




void RightRotate(RBT *rbt,Node *x)
{
  if(x->lc != rbt->nil)
    {
      Node *y = x->lc;
      x->lc = y->rc;
      if (y->rc != rbt->nil)
	y->rc->parent = x;
      y->parent = x->parent;
      if (x->parent == rbt->nil)
	rbt->root = y;
      else if (x == x->parent->lc)
	x->parent->lc = y;
      else x->parent->lc = y;
      y->rc = x;
      x->parent = y;

      x->max = GetMax(x->interval.high,x->lc->max,x->rc->max);
      y->max = GetMax(y->interval.high,y->lc->max,y->rc->max);
    }
  else cout << "Error!" << endl;
};




void RBINSERTFIXUP(RBT *rbt,Node *z)
{
  Node *y;
  while(z->parent->color == RED)
    {
      if (z->parent == z->parent->parent->lc)
	{
	  y = z->parent->parent->rc;
	  if (y->color == RED)
	    {
	      z->parent->color = BLACK;
	      y->color = BLACK;
	      z->parent->parent->color = RED;
	      z = z->parent->parent;
	    }
	  else if (z == z->parent->rc)
	    {
	      z = z->parent;
	      LeftRotate(rbt,z);
	    }
	  z->parent->color = BLACK;
	  z->parent->parent->color = RED;
	  RightRotate(rbt,z->parent->parent);
	}
      else
	{
	   y = z->parent->parent->lc;
	  if (y->color == RED)
	    {
	      z->parent->color = BLACK;
	      y->color = BLACK;
	      z->parent->parent->color = RED;
	      z = z->parent->parent;
	    }
	  else if (z == z->parent->lc)
	    {
	      z = z->parent;
	      RightRotate(rbt,z);
	    };
	  z->parent->color = BLACK;
	  z->parent->parent->color = RED;
	  LeftRotate(rbt,z->parent->parent);
	};
    };
  rbt->root->color = BLACK;
};





Node * RBINSERT(RBT *rbt,Interval interval)
{
  Node *y = rbt->nil;
  Node *x = rbt->root;
  while(x != rbt->nil)
    {
      y = x;
      if (interval.low < x->key)
	{
	  x = x->lc;
	}
      else if (interval.low > x->key)
	{
	  x = x->rc;
	}
      else return false;
    };
  Node *z;
  z->key = interval.low;
  z->parent = y;
  z->interval.low = interval.low;
  z->interval.high = interval.high;
  if (y == rbt->nil)
    rbt->root = z;
  else if (z->key < y->key)
    y->lc = z;
  else y->rc = z;
  z->lc = rbt->nil;
  z->rc = rbt->nil;
  z->color = RED;
  z->max = GetMax(interval.high,z->lc->max,z->rc->max);
  RBINSERTFIXUP(rbt,z);
};
  




Node *IntervalSearch(RBT *rbt,Interval interval)
{
  Node *x;
  x = rbt->root;
  while (x != rbt->nil && (x->interval.high < interval.low || x->interval.low >interval.high))
    {
      if (x->lc != rbt->nil && x->lc->lc->max >= interval.low)
	x = x->lc;
      else x = x->rc;
    };
  return x;
};




 void printresult(RBT *rbt,Node *m)
  {
    if (m == NULL)
      {
	cout << "not exist" << endl;
      }
    else cout << "[" << m->interval.low << "," << m->interval.high << "]" << endl;
  }





int main(int argc, char *argv[])
{
  RBT *tree;
  tree->root = tree->nil = NULL;
  Interval a,b,c,d,e,p,q,s;
  a.low = 0;
  a.high = 1;
  b.low = 1;
  b.high = 2;
  c.low = 2;
  c.high = 3;
  d.low = 3;
  d.high = 4;
  e.low = 4;
  e.high = 5;
  p.low = 0.5;
  p.high = 0.6;
  q.low = 4.5;
  q.high = 5.9;
  s.low = 5.5;
  s.high = 7.8;
  RBINSERT(tree,a);
  RBINSERT(tree,b);
  RBINSERT(tree,c);
  RBINSERT(tree,d);
  RBINSERT(tree,e);
  RBINSERT(tree,p);
  RBINSERT(tree,q);
  RBINSERT(tree,s);
  printresult(tree,IntervalSearch(tree,p));
  printresult(tree,IntervalSearch(tree,q));
  printresult(tree,IntervalSearch(tree,s));
};
